#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
using namespace std;

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int minValue = INT16_MAX;
        int pathValue = 0;
        set<pair<int,int>> S;
        DFS(heights,0,0,S,pathValue,minValue);
        return minValue;
    }
    void DFS(vector<vector<int>>& heights,int i,int j,set<pair<int,int>> S,int pathValue,int& minValue){
        if(i<0||i>=heights.size()||j<0||j>=heights[0].size()||S.find(make_pair(i,j))!=S.end()){
            return ;        
        }
        if(i==heights.size()-1&&j==heights[0].size()-1){
            minValue = min(minValue,pathValue);
            return;
        }
        if(pathValue>minValue){
            return;
        }
        S.insert(make_pair(i,j));
       
        DFS(heights,i-1,j,S,i-1>=0&&i-1<heights.size()?max(pathValue,abs(heights[i-1][j]-heights[i][j])):pathValue,minValue);
        DFS(heights,i+1,j,S,i+1>=0&&i+1<heights.size()?max(pathValue,abs(heights[i+1][j]-heights[i][j])):pathValue,minValue);
        DFS(heights,i,j-1,S,j-1>=0&&j-1<heights[0].size()?max(pathValue,abs(heights[i][j-1]-heights[i][j])):pathValue,minValue);
        DFS(heights,i,j+1,S,j+1>=0&j+1<heights[0].size()?max(pathValue,abs(heights[i][j+1]-heights[i][j])):pathValue,minValue);
    }
};

int main(){
    Solution S;
    vector<vector<int>> heights = {{1,2,1,1,1},{1,2,1,2,1},{1,2,1,2,1},{1,2,1,2,1},{1,1,1,2,1}};
    cout<<S.minimumEffortPath(heights)<<endl;
}